#include <algorithm>
#include <bits/stdc++.h>
#include <numeric>

using namespace std;

class Solution {
public:
	int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k)
	{
		vector<int> idxs, amounts { 0 };
		for (auto&& fruit : fruits) {
			idxs.emplace_back(fruit[0]);
			amounts.emplace_back(fruit[1]);
		}
		partial_sum(begin(amounts), end(amounts), begin(amounts));

		int res = 0;
		for (int l_span = k; l_span >= 0; --l_span) {
			int r_span = (k - l_span) / 2, l, r;

			l = startPos - l_span; r = startPos + r_span;
			auto firstItr(begin(idxs));
			auto left { lower_bound(begin(idxs), end(idxs), l) - firstItr },
				right { upper_bound(begin(idxs), end(idxs), r) - firstItr };
			res = max(res, amounts[right] - amounts[left]);

			l = startPos - r_span; r = startPos + l_span;
			left = lower_bound(begin(idxs), end(idxs), l) - firstItr;
			right = upper_bound(begin(idxs), end(idxs), r) - firstItr;
			res = max(res, amounts[right] - amounts[left]);
		}
		return res;
	}

private:
};

int main()
{
	[[maybe_unused]] Solution solution;
	return 0;
}
